<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>

</body>
<script>
    function BinarySerachTree() {
        // 结点类
        function Node(key) {
            this.key = key;
            this.left = null;
            this.right = null;
        }
        // 属性
        this.root = null;
        // 方法
        /* 插入操作的封装 */
        BinarySerachTree.prototype.insert = function (key) {
            // 1.创建key结点
            var newnode = new Node(key);
            // 2.判断根节点是否有值
            if (this.root == null) {
                // 2.1 若无值则将结点赋给根节点
                this.root = newnode
            } else {
                // 2.2 若有值则递归调用以此判断插入或继续递归
                this.insertNode(this.root, newnode)
            }
        }
        // 插入函数的递归函数
        BinarySerachTree.prototype.insertNode = function (node, newnode) {
            /* 
            判断路径方向
            判断是否有值，若有值，则继续递归，若无值，则赋值
            */
            if (newnode.key < node.key) {
                // 如果新节点小于根节点，则向左走
                if (node.left == null) {
                    node.left = newnode
                } else {
                    this.insertNode(node.left, newnode)
                }
            } else {
                // 如果新节点大于根节点，则向右走
                if (node.right == null) {
                    node.right = newnode
                } else {
                    this.insertNode(node.right, newnode)
                }
            }
        }


        /* 遍历方式 */
        /* 先序遍历 */
        BinarySerachTree.prototype.preOrderTravers = function (callback) {
            this.preOrderTraversNode(this.root, callback)
        }
        BinarySerachTree.prototype.preOrderTraversNode = function (nownode, callback) {
            if (nownode != null) {
                callback(nownode.key);
                // 递归调用左子树
                this.preOrderTraversNode(nownode.left, callback)
                // 左子树调用结束后直接右子树
                this.preOrderTraversNode(nownode.right, callback)
            }
        }

        /* 中序遍历 */
        BinarySerachTree.prototype.middleOrderTravers = function (callback) {
            this.middleOrderTraversNode(this.root, callback)
        }
        BinarySerachTree.prototype.middleOrderTraversNode = function (nownode, callback) {
            if (nownode != null) {
                this.middleOrderTraversNode(nownode.left, callback)
                callback(nownode.key);
                this.middleOrderTraversNode(nownode.right, callback)
            }
        }

        /* 后序遍历 */
        BinarySerachTree.prototype.postOrderTravers = function (callback) {
            this.postOrderTraversNode(this.root, callback)
        }
        BinarySerachTree.prototype.postOrderTraversNode = function (nownode, callback) {
            if (nownode != null) {
                this.postOrderTraversNode(nownode.left, callback)
                this.postOrderTraversNode(nownode.right, callback)
                callback(nownode.key);
            }
        }


        /*最大值*/
        BinarySerachTree.prototype.getmaxNode = function () {
            let node = this.root;
            while (node.right != null) {
                node = node.right
            }
            return node.key
        }
        /* 最小值 */
        BinarySerachTree.prototype.getminNode = function () {
            let node = this.root;
            while (node.left != null) {
                node = node.left
            }
            return node.key
        }


        /*搜索特定的值(递归实现)*/
        BinarySerachTree.prototype.searchThekey = function (key) {
            // 首先判断是否有值存在
            if (this.root == null) {
                return false;
            }
            // 递归操作
            return this.searchThekeyNode(this.root, key);
        }
        // 搜索特定的值的递归操作
        BinarySerachTree.prototype.searchThekeyNode = function (node, key) {
            if (node === null) {
                return false
            }
            if (key > node.key) {
                return this.searchThekeyNode(node.right, key);
            } else if (key < node.key) {
                return this.searchThekeyNode(node.left, key);
            } else {
                return true
            }
        }

        /*搜索特定的值(非递归实现)*/
        BinarySerachTree.prototype.searchThekeybywhile = function (key) {
            var node = this.root;
            if (node === null) {
                return false;
            }
            while (node != null) {
                if (key > node.key) {
                    node = node.right
                } else if (key < node.key) {
                    node = node.left
                } else {
                    return true
                }
            }
            return false
        }

        /* 移除节点 */
        BinarySerachTree.prototype.remove = function (key) {
            var current = this.root;
            var parent = this.root;
            var isLeftChild = true;
            // 查找(有则操作current，没有则返回false)
            while (current.key != key) {
                parent = current;
                if (key > current.key) {
                    isLeftChild=false
                    current = current.right
                } else {
                    isLeftChild=true
                    current = current.left
                }
                if (current == null) {
                    return false;
                }
            }
            // 第一种情况(只有一个叶子节点时)
            if (current.left == null && current.right == null) {
                if (current == this.root) {
                    this.root = null
                } else if (isLeftChild) {
                    parent.left = null
                } else {
                    parent.right = null
                }
                // 第二种情况(有一个子节点时)
            } else if (current.left == null) {
                if (current == this.root) {
                    this.root = current.right
                } else if (isLeftChild) {
                    parent.left = current.right
                } else {
                    parent.right = current.right
                }
            } else if (current.right == null) {
                if (current == this.root) {
                    this.root = current.left
                } else if (isLeftChild) {
                    parent.left = current.left
                } else {
                    parent.right = current.left
                }
            }
            // 第三种情况(有两个子结点时)
            else {
                var successor=this.getSuccssor(current);
                if (current==this.root) {
                    this.root=successor;
                }else if(isLeftChild){
                    parent.left=successor;
                }else{
                    parent.right=successor;
                }
                // 将删除结点的左子树指向当前的左子树
                successor.left=current.left
            }
            return true
        }
        BinarySerachTree.prototype.getSuccssor = function (delnode) {
            // 定义变量，保存后继
            var successor = delnode;
            // 向右走
            var current = delnode.right;
            // 后继结点的父节点
            var parentsuccessor=delnode;
            while (current != null) {
                parentsuccessor=successor;
                successor = current;
                current = current.left;
            }
            // 如果current的子节点还有子节点时
            if (successor!=delnode.right) {
                parentsuccessor.left=successor.right;
                successor.right=delnode.right
            }
            return successor;
        }

    }

    var bst = new BinarySerachTree();
    bst.insert(11)
    bst.insert(7)
    bst.insert(15)
    bst.insert(5)
    bst.insert(3)
    bst.insert(9)
    bst.insert(8)
    bst.insert(10)
    bst.insert(13)
    bst.insert(12)
    bst.insert(14)
    bst.insert(20)
    bst.insert(18)
    bst.insert(25)
    bst.insert(6)
    console.log(bst);

    var str = ''
    bst.preOrderTravers(function (key) {
        str += key + ' '
    })
    console.log('先序遍历', str);

    var str2 = ''
    bst.middleOrderTravers(function (key) {
        str2 += key + ' '
    })
    console.log('中序遍历', str2);


    var str3 = ''
    bst.postOrderTravers(function (key) {
        str3 += key + ' '
    })
    console.log('后序遍历', str3);


    // 获取最大值
    console.log(bst.getmaxNode());
    console.log(bst.getminNode());
    console.log(bst.searchThekey(23) + "结果");
    console.log(bst.searchThekeybywhile(23) + "结果");


    bst.remove(9);
    bst.remove(7);
    bst.remove(15);
    var str3 = ''
    bst.postOrderTravers(function (key) {
        str3 += key + ' '
    })
    console.log('后序遍历', str3);
</script>

</html>